To facilitate an understanding of the invention LDPC decoding and Turbo decoding will now be discussed briefly.
1. LDPC Decoders
Computationally the belief propagation LDPC decoder with log-likelihood ratio message representation requires only simple additions and subtractions except for the message transform F and F.sup.1 at the boundaries of the check node. The message transform is by far the most complex operation in the log domain LDPC decoder. It is therefore desirable to find low complexity approximation that maintains good decoding performance for all practically feasible coding rates and is at the same time computationally efficient.
Let m.sup.v2c denote the messages passed from variable node to check node, m.sup.c2v denote messages passed from check node to variable node, Y.sub.n—soft input to the decoder variable node n and X.sub.n—soft output from the decoder and D.sub.n—node degree.
The belief propagation update rule for variable node can be written as: m j v .times. .times. 2 .times. c=Y n+i .di-elect cons.[1,D].times.\.times. j .times. m i c .times. .times. 2 .times. v; v .times. .times. X n=+i .di-elect cons.[1,D].times. m i c .times. .times. 2 .times. v; (1)
Splitting the edge message into sign and magnitude values the check node update rule can be written as: s j c .times. .times. 2 .times. v=i .di-elect cons.[1,D].times.\.times. j .times. s i v .times. .times. 2 .times. c, .times. where .times. .times. s j v .times. .times. 2 .times. c, s j c .times. .times. 2 .times. v (2) are message sign bits and the sum is over GF(2) and m j c .times. .times. 2 .times. v=F−1 .times. i .di-elect cons.[1,D].times.\.times. j .times. F .function. (m i v .times. .times. 2 .times. c), .times. where .times. .times. m j v .times. .times. 2 .times. c, m j c .times. .times. 2 .times. v>0 (3) are message magnitudes and F .function. (x)=F−1 .function. (x)=−log .function. (tan . times. .times. h .function. (x2)). (4)
While it is technically possible using look-up tables to directly map F over a fixed argument interval defined by message quantization, such lookup table normally requires comparatively large hardware resources in a dedicated LDPC hardware decoder or an extra indirect memory access in a software implementation. It is also possible to compute F exactly in a software implementation but such computation typically requires multiple cycles.
By observing series of e.sup.−x expansion of transform function F F .function. (x)=2 .times. e−x+2 3 .times. e−3 .times. x+(5) and the argument x distribution densities for both F(x) and F.sup.1(x) during decoder operation it has been demonstrated that the transform functions can be effectively approximated by: {circumflex over (F)}(x)=2e.sup.−x for the forward transform, (6) F−1 .function. (x)=[−log function. (x2)]+(7) for the inverse transform, where the + at the end of the bracket means set to zero if negative, with a very little performance loss of under 0.015 dB for low rate codes (r=1/6) and nearly ideal performance for higher rate codes.
Without any loss of generality the approximation can be re-written for base-2 functions while adjusting decoder Log Likelihood Ratio (LLR) inputs by a factor of 1/log(2): {circumflex over (F)}(x)=2.times.2.sup.−x for the forward transform, (8) F−1 .function. (x)=[−log 2 .function. (x2)]+(9) for the inverse transform.
2. Turbo-Convolutional Decoder.
Convolutional codes are used as constituent codes for turbo codes. A convolutional code is usually encoded by a finite state machine and the code can be represented on a trellis. The finite state machine has K states 1, 2, . . . , K and a transition function T which given a “current” state and an information input I produces a “next” state and an output O. For example, a standard binary convolutional code with memory 4 has 16 states which may be denote using the 16 binary sequences of length 4. The states correspond to the last 4 input bits. (The initial state is 0000.) Given a current state b.sub.1b.sub.2b.sub.3b.sub.4 and input bit x, the next state is b.sub.2b.sub.3b.sub.4x. The output may be one or more bits each of which is linear function (over GF[2]) of the sequence b.sub.1b.sub.2b.sub.3b.sub.4x. In the abstract, one obtains a sequence of states S[0],S[1], . . . where S[0]=0000. For convenience we will refer to the index of the state as time. Thus S[0] is the state at time 0. The transition from the state at time t to the state at time t+1 depends on the input at time t.
Typically, each state may be reached from 2 preceding states and each state leads to 2 following states. The trellis for such a set of states is a graph with a vector of K nodes for each time t representing the K possible states at time t. Nodes are connected by edges in the graph if and only if a state transition between those states is possible. Thus, nodes at time t are connected only to nodes at time t−1 and time t+1. In the example above, and typically, each state node connects to 2 following nodes and 2 preceding nodes. The output symbols are usually transmitted through a channel. Observations of those symbols at the receiver induce probabilities on the associated transitions. In turbo decoding one attempts to compute the probabilities of the associated paths through the trellis. These are then used to compute posterior probabilities on the input bits. The algorithm that is used for this purpose is known as the BCJR algorithm.
A step in the BCJR algorithm, which can be used to implement an ideal soft-input soft-output terminated convolutional code MAP decoder used in Turbo decoding, has as one of its elementary steps the update of state probabilities as follows. Each state S in a trellis is reachable from 2 or more preceding states and can move to 2 or more subsequent states. During implementation of the BCJR algorithm one computes the probability that the encoding path entered the state S, conditioned on all information available to the left of S (e.g. from observations of variables associated to the left of S) and additionally conditioned on all information available to the right of S (e.g. from observations of variables associated to the right of S in the trellis). The state probability updates are commonly referred to as the “.alpha.” update (from the left) and the “.beta.” update (from the right). These updates have the same basic form and we will focus only on the .alpha. update.
Assume that a probability vector (p.sub.1, p.sub.2, . . . , p.sub.K) has been computed for trellis state S[t] and that this vector represents the conditional probability conditioned on all observations up to time t. E.g. p.sub.S is the posterior probability of that the trellis is in state S at time t conditioned on all observations up to time t. Observations associated to the transition from the state at time t to the state at time t+1 induce posterior probabilities on those transitions which we denote by e.g. p.sub.A2S[t] for the probability of transition from state A to state S at time t. Assuming that the states that lead to state S are state A and state B, we get
p.sub.S[t+1]=(p.sub.A[t]p.sub.A2S[t]+p.sub.B[t]p.sub.B2S[t])/Z (10) where Z is a normalization constant to enforce the constraint that the sum over the states of p.sub.S[t+1] equals 1. It is clear from this formula that to compute p.sub.S[t+1] we need only know the vector (p.sub.1, p.sub.2, . . . , p.sub.K)[t] up to a positive multiplicative constant. Similarly, the quantities p.sub.A2S[t] need only be known up to a positive multiplicative constant. Thus, in practice one does not enforce the normalization of either vector and simply definesp.sub.S[t+1]=(p.sub.A[t]p.sub.A2S[t]+p.sub.B[t]p.sub.B2S[t]) (11) where this vector is no longer required to sum to 1. Moreover, in practice it is convenient to compute not p.sub.S[t+1] but rather the logarithm of this quantity. Thus, one defines (.alpha..sub.1, .alpha..sub.2 . . . , .alpha..sub.K)[t]=(log p.sub.1, log p.sub.2, . . . , log p.sub.K)[t]. The update for this vector takes the form.alpha..sub.S[t+1]=log(exp(.alpha..sub.A[t]+.gamma..sub.A2S[t])+exp(.alph-a..sub.B[t]+.gamma..sub.B2S[t]))  (12)
The additions inside the exponential function are easily performed and we observe that the critical computation is of the form log(exp x=exp y) (13) A standard approach to computing this function is to use the identity log(exp x+exp y)=max(x,y)+log(1+exp(−|x−y|)) (14) the second quantity then being computed by e.g. a lookup table.
When there are more than 2 branches then the number of terms might be larger. For example, if there are 4 branches then the update computation takes the form log(exp u+exp v+exp x+exp y) (15)
Similar to the previous LDPC decoder example by changing input data scale the expression ( ) can be re-written using base-2 functions as:log 2(2.sup.u+2.sup.v+2.sup.x+2.sup.y)  (16)
And the arguments in the next section can be applied in a similar way.
Those skilled in the art will recognize that the same idea applies in many soft input-soft output computational components of information transmission and storage systems.
One problem with decoding operations of the type described above is the complexity involved in computing exp and log computations as part of the decoding process. Such decoding operations are normally iterative in nature which can make efficient implementation important. While exact log and exp computations may be necessary for some applications, in many LDPC and turbo decoder applications reliable approximations of the exp and/or log functions can suffice. Accordingly, there is a need for efficient hardware and/or software methods of implementing log and/or exp functions that can be used to support LDPC decoding, turbo decoding and/or one or more other applications where approximations of exp and/or log computations can be used.